// File:       map.c++
// Version:    1.00
// Author:     (c) Miles Sabin, 1997
// Purpose:    approximation to ANSI C++ map and multimap class templates

// Change log:
//  24/01/97   v. 1.00
//  23/02/97   Adapted to HoistHelper/HoistComparator split.
//  01/04/97   Added default ctor for map_value_type<K, T>.
//             Key comparator is now a hoisted binary predicate.
//             Added constructors with comparator arguments.
//  04/04/97   Replaced HoistComparators with HoistBinaryPredicates.

#include "map.h"

#include "exception.h"               // for throw
#include "hoistbp.h"
#include "hoistctdt.h"
#include "stdexcept.h"               // for out_of_range
#include "tpltutil.h"


// Implementation of map<Key, T, Compare>

#define map_type                  map<Key, T, Compare>
#define key_type                  Key
#define mapped_type               T
#define value_type                map_value_type<Key, T>
#define reference                 T&
#define const_reference           T const&
#define iterator                  map_iterator<Key, T, Compare>
#define const_iterator            map_const_iterator<Key, T, Compare>
#define rev_iterator              reverse_bidirectional_iterator<iterator, value_type, value_type&>
#define const_rev_iterator        reverse_bidirectional_iterator<const_iterator, value_type, value_type const&>
#define size_type                 size_t
#define difference_type           ptrdiff_t

#ifndef INSTANTIATE_MAP_COMPARATORS_ONLY
#ifndef INSTANTIATE_MULTIMAP_COMPARATORS_ONLY
#ifndef INSTANTIATE_MULTIMAP_NON_COMPARATORS_ONLY

template<class Key, class T, class Compare>
map<Key, T, Compare>::map()
  : tree_(get_hoist_constructor_destructor((Key*)0), &get_hoist_constructor_destructor((T*)0), new HoistBinaryPredicate<Compare, Key>(key_cmp_), false)
  {}

template<class Key, class T, class Compare>
map<Key, T, Compare>::map(Compare const& cmp)
  : key_cmp_(cmp),
    tree_(get_hoist_constructor_destructor((Key*)0), &get_hoist_constructor_destructor((T*)0), new HoistBinaryPredicate<Compare, Key>(key_cmp_), false)
  {}

template<class Key, class T, class Compare>
map<Key, T, Compare>::map(iterator const& first, iterator const& last)
  : tree_(get_hoist_constructor_destructor((Key*)0), &get_hoist_constructor_destructor((T*)0), new HoistBinaryPredicate<Compare, Key>(key_cmp_), false, first.node_, last.node_)
  {}

template<class Key, class T, class Compare>
map<Key, T, Compare>::map(iterator const& first, iterator const& last, Compare const& cmp)
  : key_cmp_(cmp),
    tree_(get_hoist_constructor_destructor((Key*)0), &get_hoist_constructor_destructor((T*)0), new HoistBinaryPredicate<Compare, Key>(key_cmp_), false, first.node_, last.node_)
  {}

template<class Key, class T, class Compare>
map<Key, T, Compare>::map(value_type const* first, value_type const* last)
  : tree_(get_hoist_constructor_destructor((Key*)0), &get_hoist_constructor_destructor((T*)0), new HoistBinaryPredicate<Compare, Key>(key_cmp_), false, first, last)
  {}

template<class Key, class T, class Compare>
map<Key, T, Compare>::map(value_type const* first, value_type const* last, Compare const& cmp)
  : key_cmp_(cmp),
    tree_(get_hoist_constructor_destructor((Key*)0), &get_hoist_constructor_destructor((T*)0), new HoistBinaryPredicate<Compare, Key>(key_cmp_), false, first, last)
  {}

template<class Key, class T, class Compare>
map<Key, T, Compare>::map(map<Key, T, Compare> const& rhs)
  : key_cmp_(rhs.key_cmp_),
    tree_(rhs.tree_, new HoistBinaryPredicate<Compare, Key>(key_cmp_))
  {}

template<class Key, class T, class Compare>
map<Key, T, Compare>::~map()
  {}

template<class Key, class T, class Compare>
const_iterator map<Key, T, Compare>::begin() const
  { return const_iterator(&tree_, tree_.begin()); }

template<class Key, class T, class Compare>
const_iterator map<Key, T, Compare>::end() const
  { return const_iterator(&tree_, tree_.end()); }

template<class Key, class T, class Compare>
const_rev_iterator map<Key, T, Compare>::rbegin() const
  { return const_rev_iterator(end()); }

template<class Key, class T, class Compare>
const_rev_iterator map<Key, T, Compare>::rend() const
  { return const_rev_iterator(begin()); }

template<class Key, class T, class Compare>
bool map<Key, T, Compare>::empty() const
  { return tree_.empty(); }

template<class Key, class T, class Compare>
size_type map<Key, T, Compare>::size() const
  { return tree_.size(); }

template<class Key, class T, class Compare>
size_type map<Key, T, Compare>::max_size() const
  { return tree_.max_size(); }

template<class Key, class T, class Compare>
size_type map<Key, T, Compare>::count(key_type const& x) const
  { return tree_.count(&x); }

template<class Key, class T, class Compare>
mapped_type const& map<Key, T, Compare>::operator[](key_type const& x) const
  {
    const_iterator p = find(x);

    if(p == end())
      throw(out_of_range("map key not present"));

    return (*p).second;
  }

template<class Key, class T, class Compare>
const_iterator map<Key, T, Compare>::find(key_type const& x) const
  { return const_iterator(&tree_, tree_.find(&x)); }

template<class Key, class T, class Compare>
const_iterator map<Key, T, Compare>::lower_bound(key_type const& x) const
  { return const_iterator(&tree_, tree_.lower_bound(&x)); }

template<class Key, class T, class Compare>
const_iterator map<Key, T, Compare>::upper_bound(key_type const& x) const
  { return const_iterator(&tree_, tree_.upper_bound(&x)); }

template<class Key, class T, class Compare>
pair<const_iterator, const_iterator> map<Key, T, Compare>::equal_range(key_type const& x) const
  {
    pair<assoc_base_node const*, assoc_base_node const*> range = tree_.equal_range(&x);
    return make_pair(const_iterator(&tree_, range.first), const_iterator(&tree_, range.second));
  }

template<class Key, class T, class Compare>
Compare map<Key, T, Compare>::key_compare() const
  { return key_cmp_; }

template<class Key, class T, class Compare>
map<Key, T, Compare>& map<Key, T, Compare>::operator=(map<Key, T, Compare> const& rhs)
  {
    tree_ = rhs.tree_;
    return *this;
  }

template<class Key, class T, class Compare>
iterator map<Key, T, Compare>::begin()
  { return iterator(&tree_, tree_.begin()); }

template<class Key, class T, class Compare>
iterator map<Key, T, Compare>::end()
  { return iterator(&tree_, tree_.end()); }

template<class Key, class T, class Compare>
rev_iterator map<Key, T, Compare>::rbegin()
  { return rev_iterator(end()); }

template<class Key, class T, class Compare>
rev_iterator map<Key, T, Compare>::rend()
  { return rev_iterator(begin()); }

template<class Key, class T, class Compare>
mapped_type& map<Key, T, Compare>::operator[](key_type const& x)
  { return (*((insert(map_value_type<Key, T>(x, T()))).first)).second; }

template<class Key, class T, class Compare>
pair<iterator, bool> map<Key, T, Compare>::insert(value_type const& x)
  {
    pair<assoc_base_node*, bool> result = tree_.insert(&x);
    return make_pair(iterator(&tree_, result.first), result.second);
  }

template<class Key, class T, class Compare>
iterator map<Key, T, Compare>::insert(iterator const& hint, value_type const& x)
  { return iterator(&tree_, tree_.insert(hint.node_, &x)); }

template<class Key, class T, class Compare>
void map<Key, T, Compare>::insert(iterator const& first, iterator const& last)
  { tree_.insert(first.node_, last.node_); }

template<class Key, class T, class Compare>
void map<Key, T, Compare>::insert(value_type const* first, value_type const* last)
  { tree_.insert(first, last); }

template<class Key, class T, class Compare>
void map<Key, T, Compare>::erase(iterator position)
  { tree_.erase(position.node_); }

template<class Key, class T, class Compare>
size_type map<Key, T, Compare>::erase(key_type const& x)
  { return tree_.erase(&x); }

template<class Key, class T, class Compare>
void map<Key, T, Compare>::erase(iterator first, iterator last)
  { tree_.erase(first.node_, last.node_); }

template<class Key, class T, class Compare>
void map<Key, T, Compare>::swap(map<Key, T, Compare>& x)
  { tree_.swap(x.tree_); }

template<class Key, class T, class Compare>
void map<Key, T, Compare>::clear()
  { tree_.clear(); }

template<class Key, class T, class Compare>
iterator map<Key, T, Compare>::find(key_type const& x)
  { return iterator(&tree_, tree_.find(&x)); }

template<class Key, class T, class Compare>
iterator map<Key, T, Compare>::lower_bound(key_type const& x)
  { return iterator(&tree_, tree_.lower_bound(&x)); }

template<class Key, class T, class Compare>
iterator map<Key, T, Compare>::upper_bound(key_type const& x)
  { return iterator(&tree_, tree_.upper_bound(&x)); }

template<class Key, class T, class Compare>
pair<iterator, iterator> map<Key, T, Compare>::equal_range(key_type const& x)
  {
    pair<assoc_base_node*, assoc_base_node*> range = tree_.equal_range(&x);
    return make_pair(iterator(&tree_, range.first), iterator(&tree_, range.second));
  }

#endif
#endif
#endif

#undef map_type
#undef key_type
#undef mapped_type
#undef value_type
#undef reference
#undef const_reference
#undef iterator
#undef const_iterator
#undef rev_iterator
#undef const_rev_iterator
#undef size_type
#undef difference_type


// Implementation of map<Key, T, Compare> free fns

#ifndef INSTANTIATE_MAP_NON_COMPARATORS_ONLY
#ifndef INSTANTIATE_MULTIMAP_COMPARATORS_ONLY
#ifndef INSTANTIATE_MULTIMAP_NON_COMPARATORS_ONLY

template<class Key, class T, class Compare>
bool operator==(map<Key, T, Compare> const& x, map<Key, T, Compare> const& y)
{
  return x.tree_.is_equal(get_hoist_equal_to_comparator((Key*)0), &get_hoist_equal_to_comparator((T*)0), y.tree_);
}

template<class Key, class T, class Compare>
bool operator< (map<Key, T, Compare> const& x, map<Key, T, Compare> const& y)
{
  return x.tree_.is_less_than(get_hoist_less_comparator((Key*)0), &get_hoist_less_comparator((T*)0), y.tree_);
}

#endif
#endif
#endif

// Implementation of map_iterator

#ifndef INSTANTIATE_MAP_COMPARATORS_ONLY
#ifndef INSTANTIATE_MULTIMAP_COMPARATORS_ONLY

template<class Key, class T, class Compare>
map_iterator<Key, T, Compare>::map_iterator(map_iterator<Key, T, Compare> const& rhs)
  : tree_(rhs.tree_),
    node_(rhs.node_)
  {}

template<class Key, class T, class Compare>
map_iterator<Key, T, Compare>& map_iterator<Key, T, Compare>::operator=(map_iterator<Key, T, Compare> const& rhs)
  {
    tree_ = rhs.tree_;
    node_ = rhs.node_;
    return *this;
  }

template<class Key, class T, class Compare>
map_iterator<Key, T, Compare>& map_iterator<Key, T, Compare>::operator++()
  {
    node_ = tree_->successor(node_);
    return *this;
  }

template<class Key, class T, class Compare>
map_iterator<Key, T, Compare> map_iterator<Key, T, Compare>::operator++(int)
  {
    assoc_base_node* current_node = node_;
    node_ = tree_->successor(node_);
    return map_iterator<Key, T, Compare>(tree_, current_node);
  }

template<class Key, class T, class Compare>
map_iterator<Key, T, Compare>& map_iterator<Key, T, Compare>::operator--()
  {
    node_ = tree_->predecessor(node_);
    return *this;
  }

template<class Key, class T, class Compare>
map_iterator<Key, T, Compare> map_iterator<Key, T, Compare>::operator--(int)
  {
    assoc_base_node* current_node = node_;
    node_ = tree_->predecessor(node_);
    return map_iterator<Key, T, Compare>(tree_, current_node);
  }


// Implementation of map_const_iterator

template<class Key, class T, class Compare>
map_const_iterator<Key, T, Compare>::map_const_iterator(map_const_iterator<Key, T, Compare> const& rhs)
  : tree_(rhs.tree_),
    node_(rhs.node_)
  {}

template<class Key, class T, class Compare>
map_const_iterator<Key, T, Compare>& map_const_iterator<Key, T, Compare>::operator=(map_const_iterator<Key, T, Compare> const& rhs)
  {
    tree_ = rhs.tree_;
    node_ = rhs.node_;
    return *this;
  }

template<class Key, class T, class Compare>
map_const_iterator<Key, T, Compare>& map_const_iterator<Key, T, Compare>::operator++()
  {
    node_ = tree_->successor(node_);
    return *this;
  }

template<class Key, class T, class Compare>
map_const_iterator<Key, T, Compare> map_const_iterator<Key, T, Compare>::operator++(int)
  {
    assoc_base_node const* current_node = node_;
    node_ = tree_->successor(node_);
    return map_const_iterator<Key, T, Compare>(tree_, current_node);
  }

template<class Key, class T, class Compare>
map_const_iterator<Key, T, Compare>& map_const_iterator<Key, T, Compare>::operator--()
  {
    node_ = tree_->predecessor(node_);
    return *this;
  }

template<class Key, class T, class Compare>
map_const_iterator<Key, T, Compare> map_const_iterator<Key, T, Compare>::operator--(int)
  {
    assoc_base_node const* current_node = node_;
    node_ = tree_->predecessor(node_);
    return map_const_iterator<Key, T, Compare>(tree_, current_node);
  }

#endif
#endif


// Implementation of multimap<Key, T, Compare>

#define multimap_type             multimap<Key, T, Compare>
#define key_type                  Key
#define mapped_type               T
#define value_type                map_value_type<Key, T>
#define reference                 T&
#define const_reference           T const&
#define iterator                  multimap_iterator<Key, T, Compare>
#define const_iterator            multimap_const_iterator<Key, T, Compare>
#define rev_iterator              reverse_bidirectional_iterator<iterator, value_type, value_type&>
#define const_rev_iterator        reverse_bidirectional_iterator<const_iterator, value_type, value_type const&>
#define size_type                 size_t
#define difference_type           ptrdiff_t

#ifndef INSTANTIATE_MULTIMAP_COMPARATORS_ONLY
#ifndef INSTANTIATE_MAP_COMPARATORS_ONLY
#ifndef INSTANTIATE_MAP_NON_COMPARATORS_ONLY

template<class Key, class T, class Compare>
multimap<Key, T, Compare>::multimap()
  : tree_(get_hoist_constructor_destructor((Key*)0), &get_hoist_constructor_destructor((T*)0), new HoistBinaryPredicate<Compare, Key>(key_cmp_), true)
  {}

template<class Key, class T, class Compare>
multimap<Key, T, Compare>::multimap(Compare const& cmp)
  : key_cmp_(cmp),
    tree_(get_hoist_constructor_destructor((Key*)0), &get_hoist_constructor_destructor((T*)0), new HoistBinaryPredicate<Compare, Key>(key_cmp_), true)
  {}

template<class Key, class T, class Compare>
multimap<Key, T, Compare>::multimap(iterator const& first, iterator const& last)
  : tree_(get_hoist_constructor_destructor((Key*)0), &get_hoist_constructor_destructor((T*)0), new HoistBinaryPredicate<Compare, Key>(key_cmp_), true, first.node_, last.node_)
  {}

template<class Key, class T, class Compare>
multimap<Key, T, Compare>::multimap(iterator const& first, iterator const& last, Compare const& cmp)
  : key_cmp_(cmp),
    tree_(get_hoist_constructor_destructor((Key*)0), &get_hoist_constructor_destructor((T*)0), new HoistBinaryPredicate<Compare, Key>(key_cmp_), true, first.node_, last.node_)
  {}

template<class Key, class T, class Compare>
multimap<Key, T, Compare>::multimap(value_type const* first, value_type const* last)
  : tree_(get_hoist_constructor_destructor((Key*)0), &get_hoist_constructor_destructor((T*)0), new HoistBinaryPredicate<Compare, Key>(key_cmp_), true, first, last)
  {}

template<class Key, class T, class Compare>
multimap<Key, T, Compare>::multimap(value_type const* first, value_type const* last, Compare const& cmp)
  : key_cmp_(cmp),
    tree_(get_hoist_constructor_destructor((Key*)0), &get_hoist_constructor_destructor((T*)0), new HoistBinaryPredicate<Compare, Key>(key_cmp_), true, first, last)
  {}

template<class Key, class T, class Compare>
multimap<Key, T, Compare>::multimap(multimap<Key, T, Compare> const& rhs)
  : key_cmp_(rhs.key_cmp_),
    tree_(rhs.tree_, new HoistBinaryPredicate<Compare, Key>(key_cmp_))
  {}

template<class Key, class T, class Compare>
multimap<Key, T, Compare>::~multimap()
  {}

template<class Key, class T, class Compare>
const_iterator multimap<Key, T, Compare>::begin() const
  { return const_iterator(&tree_, tree_.begin()); }

template<class Key, class T, class Compare>
const_iterator multimap<Key, T, Compare>::end() const
  { return const_iterator(&tree_, tree_.end()); }

template<class Key, class T, class Compare>
const_rev_iterator multimap<Key, T, Compare>::rbegin() const
  { return const_rev_iterator(end()); }

template<class Key, class T, class Compare>
const_rev_iterator multimap<Key, T, Compare>::rend() const
  { return const_rev_iterator(begin()); }

template<class Key, class T, class Compare>
bool multimap<Key, T, Compare>::empty() const
  { return tree_.empty(); }

template<class Key, class T, class Compare>
size_type multimap<Key, T, Compare>::size() const
  { return tree_.size(); }

template<class Key, class T, class Compare>
size_type multimap<Key, T, Compare>::max_size() const
  { return tree_.max_size(); }

template<class Key, class T, class Compare>
const_iterator multimap<Key, T, Compare>::find(key_type const& x) const
  { return const_iterator(&tree_, tree_.find(&x)); }

template<class Key, class T, class Compare>
size_type multimap<Key, T, Compare>::count(key_type const& x) const
  { return tree_.count(&x); }

template<class Key, class T, class Compare>
const_iterator multimap<Key, T, Compare>::lower_bound(key_type const& x) const
  { return const_iterator(&tree_, tree_.lower_bound(&x)); }

template<class Key, class T, class Compare>
const_iterator multimap<Key, T, Compare>::upper_bound(key_type const& x) const
  { return const_iterator(&tree_, tree_.upper_bound(&x)); }

template<class Key, class T, class Compare>
pair<const_iterator, const_iterator> multimap<Key, T, Compare>::equal_range(key_type const& x) const
  {
    pair<assoc_base_node const*, assoc_base_node const*> range = tree_.equal_range(&x);
    return make_pair(const_iterator(&tree_, range.first), const_iterator(&tree_, range.second));
  }

template<class Key, class T, class Compare>
Compare multimap<Key, T, Compare>::key_compare() const
  { return key_cmp_; }

template<class Key, class T, class Compare>
multimap<Key, T, Compare>& multimap<Key, T, Compare>::operator=(multimap<Key, T, Compare> const& rhs)
  {
    tree_ = rhs.tree_;
    return *this;
  }

template<class Key, class T, class Compare>
iterator multimap<Key, T, Compare>::begin()
  { return iterator(&tree_, tree_.begin()); }

template<class Key, class T, class Compare>
iterator multimap<Key, T, Compare>::end()
  { return iterator(&tree_, tree_.end()); }

template<class Key, class T, class Compare>
rev_iterator multimap<Key, T, Compare>::rbegin()
  { return rev_iterator(end()); }

template<class Key, class T, class Compare>
rev_iterator multimap<Key, T, Compare>::rend()
  { return rev_iterator(begin()); }

template<class Key, class T, class Compare>
pair<iterator, bool> multimap<Key, T, Compare>::insert(value_type const& x)
  {
    pair<assoc_base_node*, bool> result = tree_.insert(&x);
    return make_pair(iterator(&tree_, result.first), result.second);
  }

template<class Key, class T, class Compare>
iterator multimap<Key, T, Compare>::insert(iterator const& hint, value_type const& x)
  { return iterator(&tree_, tree_.insert(hint.node_, &x)); }

template<class Key, class T, class Compare>
void multimap<Key, T, Compare>::insert(iterator const& first, iterator const& last)
  { tree_.insert(first.node_, last.node_); }

template<class Key, class T, class Compare>
void multimap<Key, T, Compare>::insert(value_type const* first, value_type const* last)
  { tree_.insert(first, last); }

template<class Key, class T, class Compare>
void multimap<Key, T, Compare>::erase(iterator position)
  { tree_.erase(position.node_); }

template<class Key, class T, class Compare>
size_type multimap<Key, T, Compare>::erase(key_type const& x)
  { return tree_.erase(&x); }

template<class Key, class T, class Compare>
void multimap<Key, T, Compare>::erase(iterator first, iterator last)
  { tree_.erase(first.node_, last.node_); }

template<class Key, class T, class Compare>
void multimap<Key, T, Compare>::swap(multimap<Key, T, Compare>& x)
  { tree_.swap(x.tree_); }

template<class Key, class T, class Compare>
void multimap<Key, T, Compare>::clear()
  { tree_.clear(); }

template<class Key, class T, class Compare>
iterator multimap<Key, T, Compare>::find(key_type const& x)
  { return iterator(&tree_, tree_.find(&x)); }

template<class Key, class T, class Compare>
iterator multimap<Key, T, Compare>::lower_bound(key_type const& x)
  { return iterator(&tree_, tree_.lower_bound(&x)); }

template<class Key, class T, class Compare>
iterator multimap<Key, T, Compare>::upper_bound(key_type const& x)
  { return iterator(&tree_, tree_.upper_bound(&x)); }

template<class Key, class T, class Compare>
pair<iterator, iterator> multimap<Key, T, Compare>::equal_range(key_type const& x)
  {
    pair<assoc_base_node*, assoc_base_node*> range = tree_.equal_range(&x);
    return make_pair(iterator(&tree_, range.first), iterator(&tree_, range.second));
  }

#endif
#endif
#endif

#undef multimap_type
#undef key_type
#undef mapped_type
#undef value_type
#undef reference
#undef const_reference
#undef iterator
#undef const_iterator
#undef rev_iterator
#undef const_rev_iterator
#undef size_type
#undef difference_type


// Implementation of multimap<Key, T, Compare> free fns

#ifndef INSTANTIATE_MULTIMAP_NON_COMPARATORS_ONLY
#ifndef INSTANTIATE_MAP_COMPARATORS_ONLY
#ifndef INSTANTIATE_MAP_NON_COMPARATORS_ONLY

template<class Key, class T, class Compare>
bool operator==(multimap<Key, T, Compare> const& x, multimap<Key, T, Compare> const& y)
{
  return x.tree_.is_equal(get_hoist_equal_to_comparator((Key*)0), &get_hoist_equal_to_comparator((T*)0), y.tree_);
}

template<class Key, class T, class Compare>
bool operator< (multimap<Key, T, Compare> const& x, multimap<Key, T, Compare> const& y)
{
  return x.tree_.is_less_than(get_hoist_less_comparator((Key*)0), &get_hoist_less_comparator((T*)0), y.tree_);
}

#endif
#endif
#endif
